The present invention relates to the software garbage collection, and, more particularly, to optimizing a marking phase in mark-sweep garbage collectors by reducing paging activity.
Garbage collection is a form of automatic memory management that reclaims garbage, which is memory used by objects that are not reachable. A reachable object can be defined as an object for which there exists some variable in the program environment that leads to it, either directly or through references from other reachable objects. Assuming objects are stored in a heap, garbage objects are objects which have no references pointing to them. Anything referenced from a reachable object is itself reachable, meaning that reachability is a transitive closure.
The heap is a portion of memory allocated for objects, which can be managed by a memory manager. A heap can be a virtual memory space, which means that the heap size can be greater than an amount of physical random access memory (RAM) dedicated to the heap. When heap memory exceeds dedicated RAM, a less desirable memory (e.g., hard drive memory) is used to satisfy the difference. Paging is a technique used by many virtual memory managers to move sections of memory, called pages, between the RAM and the less desirable memory, which can be referred to as a secondary memory. When a garbage collected application does not fit in RAM and paging is needed, performance degrades substantially.
That is, execution of conventional garbage collection program can result in an excessive swapping of pages of memory back and forth between RAM and secondary memory, which is often referred to as thrashing. This type of thrashing can result from a lack of cooperation between the garbage collector and a virtual memory manager. Garbage collectors can be classified into four categories, VM-oblivious, VM-sensitive, VM-aware, and VM-cooperative) based upon their relationship with a virtual memory manager. VM-oblivious garbage collectors, which includes most traditional garbage collectors, ignore virtual memory altogether.
VM-sensitive garbage collectors take steps to limit paging problems, yet do not permit communications between a garbage collector and a virtual memory manager. VM-sensitive garbage collections can include generational garbage collectors and ephemeral garbage collectors. In either, a majority of garbage collection cycles (e.g., minor cycles) can execute that do not traverse an entire object map, yet still reclaim a majority of unreachable objects. Generational garbage collectors will occasionally execute a major cycle, which takes longer than a minor cycle yet which traverses the entire object map. Major cycles are more likely to result in paging problems.
Real-world implementations of VM-aware and VM-cooperative garbage collectors are scarce. VM-aware garbage collectors permit unidirectional communication between garbage collectors and a virtual memory manager. Academic foundations for this type of garbage collection exists (references included in the information disclosure statement (IDS) accompanying the instant application).
VM-cooperative garbage collectors permit bidirectional communication between garbage collectors and a virtual memory manager. Academic foundations for this type of garbage collection exists, specifically in a paper titled “Page-Level Cooperative Garbage Collection” (reference included in the IDS accompanying the instant application), which describes a Hippocratic Collector (HC).
The HC divides the heap into superpages, which are aligned groups of similar pages. The HC communicates with the virtual memory manager only under memory pressure. When notified by the virtual memory manager that increased memory pressure will soon cause paging, the HC works to keep heap memory resident and avoid mutator page faults. When heap pages must be evicted, a “book-marking” algorithm allows HC to collect only those objects in main memory and eliminates page faults caused by the garbage collector. One significant drawback to the HC is that bookmarked objects must be treated as reachable, so the HC will not be able to reclaim all unused space.